package com.example.algorithm;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 最佳页面替换算法
 *
 * @author huahua
 * @DATE 2024/6/30
 **/
public class OPT {

    public static void main(String[] args) {
        System.out.println(queryDataBase(2, new int[]{1, 2, 3, 1, 2, 3}));
    }

    /**
     * 数据库缓存
     * 模拟访问规则如下：
     * 当查询值在缓存中，直接访问缓存，不访问数据库。否则，访问数据库，并将值放入缓存。
     * 若缓存已满，则必须删除一个缓存。
     * 给定缓存大小和训练数据，依次模拟访问这组数据，请分析在此访问规则下最少的数据库访问次数
     * 输入
     * 2
     * 1 2 3 1 2 3
     * 输出
     * 4
     */
    public static int queryDataBase(int cacheSize, int[] ids) {
        // 操作系统OPT算法，最优的删除策略
        // 如果当前缓存中某个元素在之后不会被使用到，那么可以将其删除
        // 如果当前缓存中所有元素在之后的都会使用到，那么删除“最晚使用到”的那个元素
        // 这样才能使得访问数据库总数最少
        if (ids.length == 0) {
            return 0;
        }
        HashSet<Integer> cache = new HashSet<>();
        int queryCount = 0;
        for (int i = 0; i < ids.length; i++) {
            if (cache.contains(ids[i])) {
                continue;
            }

            if (cache.size() < cacheSize) {
                // 缓存空间有剩余
                cache.add(ids[i]);
                queryCount++;
            } else {
                // 缓存空间已满
                queryCount++;
                int delNum = getDelNum(cache, ids, i + 1);
                cache.remove(delNum);
                cache.add(ids[i]);
            }
        }
        return queryCount;
    }

    // 在从start之后的ids中找到需要删除的元素
    private static int getDelNum(HashSet<Integer> cache, int[] ids, int start) {
        List<Integer> remainList = new ArrayList<>();
        for (int i = start; i < ids.length; i++) {
            remainList.add(ids[i]);
        }

        // 优先返回缓存的值在后续数组中不会再出现的值
        for (Integer num : cache) {
            if (!remainList.contains(num)) {
                return num;
            }
        }

        // 删除“最晚使用到”的那个元素
        int lastIndex = 0;
        for (Integer num : cache) {
            for (int i = 0; i < remainList.size(); i++) {
                if (remainList.get(i) == num) {
                    lastIndex = Math.max(lastIndex, i);
                    break;
                }
            }
        }
        return remainList.get(lastIndex);
    }
}
